package reBuildBinaryTree;

import java.util.Stack;

public class Solution3 {
    public static void main(String[] args) {
        int[] pre = {1,2,3,4,5,6,7};
        int[] mid = {3,2,4,1,6,5,7};
        Solution3 solution3 = new Solution3();
        Main main = new Main();
        TreeNode head = solution3.reConstructBinaryTree(new int[]{1, 2, 4, 7, 3, 5, 6, 8}, new int[]{4, 7, 2, 1, 5, 3, 8, 6});
//        main.frontForTree();
    }
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            if (pre.length == 0)
                return null;
            Stack<TreeNode> stack = new Stack<>();
            //前序的第一个其实就是根节点
            TreeNode root = new TreeNode(pre[0]);
            TreeNode cur = root;
            for (int i = 1, j = 0; i < pre.length; i++) {
                //第一种情况,如何 pre[0] == in[0] 则说明根节点没有左子树
                if (cur.val != in[j]) {
                    cur.left = new TreeNode(pre[i]);
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    //第二种情况
                    j++;
                    //找到合适的cur，然后确定他的右节点
                    while (!stack.empty() && stack.peek().val == in[j]) {
                        cur = stack.pop();
                        j++;
                    }
                    //给cur添加右节点
                    cur = cur.right = new TreeNode(pre[i]);
                }
            }
            return root;
        }
  public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
